package com.xxwy.lintcodes;

import com.xxwy.Twopoints;
import jdk.nashorn.internal.objects.NativeNumber;

/**
 * @author xxwy
 * partition array
 * 给出一个整数数组 nums 和一个整数 k。划分数组（即移动数组 nums 中的元素），使得：
 * <p>
 * 所有小于k的元素移到左边
 * 所有大于等于k的元素移到右边
 * 返回数组划分的位置，即数组中第一个位置 i，满足 nums[i] 大于等于 k。
 * <p>
 * 给出数组 nums = [3,2,2,1] 和 k = 2，返回 1.
 * 挑战
 * 使用 O(n) 的时间复杂度在数组上进行划分。
 */
@Twopoints
public class Num31 {

    public int partitionArray(int[] nums, int k) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int j = 0;
        int g = nums.length - 1;
        while (true) {
            while (j <= nums.length - 1 && nums[j] < k) {
                j++;
            }
            while (g >= 0 && nums[g] >= k) {
                g--;
            }
            if (j > g) {
                break;
            }
            int temp = nums[j];
            nums[j] = nums[g];
            nums[g] = temp;
            j++;
            g--;
        }
        if (j < nums.length && nums[j] <k) {
            return j + 1;
        }
        return j;
    }

    public int partitionArray2(int[] nums, int k) {
        // write your code here
        int l = 0;
        int r = nums.length - 1;

        while (l<r){
            while (l <r && nums[l] <k){
                l++;
            }
            while (l<r && nums[r]>=k){
                r--;
            }
            if(l<r){
                int temp = nums[r];
                nums[r] = nums[l];
                nums[l] = temp;
                l++;
                r--;
            }
        }

        if (l < nums.length && nums[l] <k) {
            return l + 1;
        }

        return l;
    }

    public static void main(String[] args) {
        new Num31().partitionArray(new int[]{7, 7, 9, 8, 6, 6, 8, 7, 9, 8, 6, 8}, 10);
    }

}
